import java.util.*;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class solution {

    /*public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<Node, Node>();
        Node cur=head;
            while(cur != null) {
                Node node = new Node(cur.val);
                map.put(cur,node);
                cur = cur.next;
            }

            //2. 再次遍历链表
            cur = head;
            while(cur != null) {
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
    }*/


    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int cur=nums[i];
            if (set.contains(cur)){
                return true;
            }
            set.add(cur);
        }
        return false;
    }

    /**
     * 存在重复元素
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num=nums[i];
            if (map.containsKey(num)&&i-map.get(num)<=k){
                return true;
            }
            map.put(num,i);
        }
        return false;
    }

    /**
     * 此方法时间超了
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i]==nums[j]&&Math.abs(i-j)<=k&&i!=j){
                    return true;
                }
            }
        }
        return false;
    }

    //统计topk个频率高的
    public List<String> topKFrequent(String[] words, int k) {
        //统计每个单词出现的次数
        HashMap<String,Integer> map=new HashMap<>();
        for(String s:words){
            if (!map.containsKey(s)){
                map.put(s,1);
            }else{
                int cur=map.get(s);
                map.put(s,cur+1);
            }
        }
        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());//根据key变成大根堆
                }
                return o1.getValue().compareTo(o2.getValue());
            }


        });

        for(Map.Entry<String,Integer> x: map.entrySet()){
            //若未放满，直接放入
            if (minHeap.size()<k){
                minHeap.offer(x);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();
                if (top.getValue().compareTo(x.getValue())==0){
                    if (top.getKey().compareTo(x.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(x);
                    }
                }else{
                    if (x.getValue().compareTo(top.getValue())>0){
                        minHeap.poll();
                        minHeap.offer(x);
                    }
                }
            }
            //若已满，则需先每次比较栈顶元素
        }

        List<String> list=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> temp=minHeap.poll();
            list.add(temp.getKey());
        }
        Collections.reverse(list);
        return list;
    }

    /**
     * 坏键盘打字
     */
    public void brokenBoard(){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextLine()){
            String sShould=sc.nextLine();
            String sFact=sc.nextLine();
            HashSet<Character> set=new HashSet<>();
            HashSet<Character> setB=new HashSet<>();
            for(char ch : sFact.toUpperCase().toCharArray()) {
                set.add(ch);
            }
            for (char ch:sShould.toUpperCase().toCharArray()){
                if (!setB.contains(ch)&&!set.contains(ch)){
                    System.out.print(ch);
                    setB.add(ch);
                }
            }
        }
    }

    /**
     * 宝石与石头
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set=new HashSet<>();
        int count=0;
        for (int i = 0; i < jewels.length(); i++) {
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        for (int i = 0; i < stones.length(); i++) {
            char ch=stones.charAt(i);
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    /**
     * 寻找只出现一次的数字，当然最简方法是用^
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        TreeSet<Integer> set=new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])){
                set.add(nums[i]);
            }else{
                set.remove(nums[i]);
            }
        }
        return set.pollFirst();
    }
}
